package luo.hui.jiang.binarysearchoecursion.dynamic;

/**
 * @author 罗惠江
 * @version 1.0
 * @email 1511619294@qq.com
 * @date 2020/8/20 16:26
 */
public class KnapsackProblem {
	public static void main(String[] args) {
		int[] w = {1, 4, 3};// 物品重量
		int[] val = {1500, 3000, 2000}; // 物品价值，这里val[i]
		int m = 4;// 物品的容量
		int n = val.length; // 物品的个数

		// 创建二维数组
		// 最大价值
		int[][] v = new int[n + 1][m + 1];
		// 记录商品情况
		int[][] path = new int[n + 1][m + 1];
		for (int i = 0; i < v.length; i++) {
			v[i][0] = 0;
			v[0][i] = 0;
		}

		// 根据公式进行动态规划处理
		for (int i = 1; i < v.length; i++) {
			for (int j = 0; j < v[0].length; j++) {
				if (w[i - 1] > j) {
					v[i][j] = v[i - 1][j];
				} else {
					if (v[i - 1][j] < val[i - 1] + v[i - 1][j - w[i - 1]]) {

						// 这里是关键的地方！！！！
						/**
						 *
						 *    0    0    0    0    0
						 *    0 1500 1500 1500 1500
						 *    0 1500 1500 1500 3000
						 *    0 1500 1500 2000 3500
						 *
						 *    所里一下思路 其实他的用意就是
						 *    右边要大于左边。
						 *    下面的要大于上面的。
						 *    我们看到最后一个3500
						 *    他就需要调用下面的语句，具体是干嘛呢 ?
						 *    解析：横坐标来表示我们的货物，纵坐标其实就很巧妙的是我们拥有的容量
						 *    v[i] 表示我们货物的价值
						 *    w[i] 表示重量。
						 *    所以我们会看到最上面吸纳 w[i] 和 j 比较。 如果 w[i] 比 j 小那就说明我们还有多余的空间
						 *    则需需要在次比较，看看我们的商品价值和剩余容量的价值加起来，会不会上一次个容量的价值大。
						 *    如果会，才将商品添加进来。
						 *
						 */
						v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];
						path[i][j] = 1;
					} else {
						v[i][j] = v[i - 1][j];
					}
				}
			}
		}
		for (int i = 0; i < v.length; i++) {
			for (int j = 0; j < v[i].length; j++) {
				System.out.printf("%4d ", v[i][j]);
			}
			System.out.println();
		}

		int i = path.length - 1;//行最大的下标
		int j = path[0].length - 1;// 列的最大下标
		while (i > 0 && j > 0) {
			if (path[i][j] == 1) {
				System.out.printf("第%d个商品放入到背包", i);
				j -= w[i - 1];
			}
			i--;
		}
	}
}
